package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.List;

import org.junit.jupiter.api.Test;

/**
 * 78. 子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * <p>
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 * <p>
 * <p>
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * <p>
 * 示例 2：
 * 输入：nums = [0]
 * 输出：[[],[0]]
 * <p>
 * <p>
 * 提示：
 * 1 <= nums.length <= 10
 * -10 <= nums[i] <= 10
 * nums 中的所有元素 互不相同
 * <p>
 * https://leetcode.cn/problems/subsets/
 *
 * @author jiangfeng on 2022/6/19
 */
public class SubSets {

    @Test
    public void test() {
        System.out.println(subsets2(new int[] {1, 2, 3}));
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] exist = new boolean[nums.length];

        sub(nums, exist, 0, false, res);
        sub(nums, exist, 0, true, res);
        return res;
    }

    public void sub(int[] nums, boolean[] exist, int j, boolean select, List<List<Integer>> res) {
        if (j == nums.length) {
            return;
        }
        exist[j] = select;
        if (j < nums.length - 1) {
            sub(nums, exist, j + 1, false, res);
            sub(nums, exist, j + 1, true, res);
        }

        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (exist[i]) {
                temp.add(nums[i]);
            }
        }
        res.add(temp);

    }

    /**
     * ..............
     */


    public List<List<Integer>> subsets2(int[] nums) {
        boolean[] exist = new boolean[nums.length];
        List<List<Integer>> res = new ArrayList<>();
        //int len =  Math.pow(2,nums.length);

        sub2(nums, exist, 0, false, res);
        sub2(nums, exist, 0, true, res);
        return res;
    }

    // 被记录影响了.不同分支会相互影响boolean.
    public void sub2(int[] nums, boolean[] exist, int j, boolean select, List<List<Integer>> res) {
        if (j == nums.length) {
            return;
        }
        exist[j] = select;
        if (j == nums.length - 1) {
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if (exist[i]) {
                    temp.add(nums[i]);
                }
            }
            res.add(temp);
        }

        sub2(nums, exist, j + 1, false, res);
        sub2(nums, exist, j + 1, true, res);

    }


}
